package com.mlh.string;

/**
 * @author 缪林辉
 * @date 2024/2/29 13:03
 * @DESCRIPTION
 * 给你两个字符串 haystack 和 needle ，请你在 haystack字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0开始）。
 * 如果 needle 不是 haystack 的一部分，则返回  -1 。
 * 输入：haystack = "sadbutsad", needle = "sad"
 * 输出：0
 * 解释："sad" 在下标 0 和 6 处匹配。
 * 第一个匹配项的下标是 0 ，所以返回 0 。
 */
public class StrStr {
    //haystack是文本串
    //needle是模式串
    public int method1(String haystack, String needle) {
        int[] next = kmpNext(needle);
        for (int i = 0, j = 0; i < haystack.length(); i++) {
            // 模式串是 j 与文本串是 i
            // 当str1.charAt(i)!=str2.charAt(j),去修改j的大小，i是不去修改的
            //在寻找可配对上的字符，如果配对上了  或者寻找到0位置了  则退出循环
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            //配对上了就将j向后推一位继续  i的话会通过for循环来向后推一位
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == needle.length()) {// 在文本串中成功找到了模式串
                return i - j + 1;
            }
        }
        return -1;
    }

    // 算出一个字符串的部分匹配值的方法
    public static int[] kmpNext(String dest) {
        // 创建一个next 数组保存部分匹配值
        int[] next = new int[dest.length()];
        next[0] = 0;// 如果模式串的长度为1，部分匹配值就为0
        for (int i = 1, j = 0; i < dest.length(); i++) {
            // 当dest.charAt(i)!=dest.charAt(j),我们需要从next[j-1]获取新的
            // 直到我们发现有dest.charAt(i)==dest.charAt(j)成立或者j<0才退出
            // 这是kmp算法的核心代码
            while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
                j = next[j - 1];
            }
            // 当dest.charAt(i)==dest.charAt(j)满足时，部分匹配值+1
            if (dest.charAt(i) == dest.charAt(j)) {
                j++;
            }
            next[i] = j;//此时j保存的就是上一个next[i]的值
        }
        return next;
    }
}
